package demo.practice.backtrack;

import java.util.HashMap;
import java.util.Map;

public class P322 {

    Map<Integer,Integer> map= new HashMap<>();

    public static void main(String[] args) {
        P322 p322= new P322();
        p322.coinChange(new int[]{1,2,5},11);
    }

    public int coinChange(int[] coins, int amount) {
        if(map.containsKey(amount)){
            return map.get(amount);
        }
        if(amount==0){
            return 0;
        }
        if(amount<0){
            return -1;
        }
        int min=Integer.MAX_VALUE;
        for(Integer i :coins){
            int ch=coinChange(coins,amount-i);
            if(ch>=0)
                min= Math.min(ch+1,min);
        }
        if(min==Integer.MAX_VALUE)
            min=-1;

        map.put(amount,min);
        return min;
    }





}
